#include <cstring>
#include "dfa_construct.h"
#include "vertex_queue.h"
#include "grate_constants.h"

const int LAST_MASK = (15 << 28);
const int LF_MASK = (1<<28) - 1;
int * lf_last; // Failure function + incoming letter

vertex_queue * vert_queue;

inline void set_last(int v, char c){
  lf_last[v] &= ~LAST_MASK;
  lf_last[v] |= ((int)(c) << 28);
}

inline char get_last(int v){
  char z = (((lf_last[v] & LAST_MASK) >> 28) & LONG_MASK);
  return (z == 15) ? -1 : z;
}

inline void set_lf(int v, int clf){
  lf_last[v] &= ~LF_MASK;
  lf_last[v] |= clf;
}

inline int get_lf(int v){
  return lf_last[v] & LF_MASK;
}

void construct_dfa(dfa * DFA){
  int alph_size = DFA->alph_size;
  int total = DFA->total;

  lf_last = new int [total + 1];
  memset(lf_last, 0, sizeof(int) * (total + 1));

  vert_queue = new vertex_queue(DFA->words_num);

  vert_queue->push_vertex(1);
  set_last(1, -1);
  set_lf(1, 1);

  while (!vert_queue->is_empty()){
    construct_vertex(DFA, vert_queue->pop_vertex());
  }

  delete[] lf_last;
  delete vert_queue;
}

void construct_vertex(dfa * DFA, int v){
  int alph_size = DFA->alph_size;
  int c;
  for (c=0; c<alph_size; c++){
    if (!(*DFA)[v][c]){
      (*DFA)[v][c] = (*DFA)[get_lf(v)][c];
    }
    else{
      int u = (*DFA)[v][c];
      if (u < 0){
        (*DFA)[v][c] = 0;
        continue;
      }
      vert_queue->push_vertex(u);
      set_last(u, c);
      set_lf(u, (v == 1) ? 1 : (*DFA)[get_lf(v)][c]);
    }
  }
}

// DEBUGGING PURPOSES!!!
/*void read_word(const char * word){
  int cv = 1, i;
  for (i=0; word[i]; i++){
    int c = get_sigma(cv, word[i] - 'a');
    if (!dfa[cv*ALPH_SIZE + c]){
      c=c;
    }
    else cv = dfa[cv*ALPH_SIZE + c];
  }
}*/